<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: pq_tree.h Source File</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li><a href="classes.html"><span>Classes</span></a></li>
    <li class="current"><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<h1>pq_tree.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">//   pq_tree.h</span>
<a name="l00004"></a>00004 <span class="comment">//</span>
<a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
<a name="l00006"></a>00006 <span class="comment">// $Id: pq_tree.h,v 1.20 2008/02/03 18:17:08 chris Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef PQ_TREE_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define PQ_TREE_H</span>
<a name="l00010"></a>00010 <span class="preprocessor"></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
<a name="l00012"></a>00012 <span class="preprocessor">#include &lt;GTL/pq_node.h&gt;</span>
<a name="l00013"></a>00013 <span class="preprocessor">#include &lt;GTL/embedding.h&gt;</span>
<a name="l00014"></a>00014 <span class="preprocessor">#include &lt;GTL/debug.h&gt;</span>
<a name="l00015"></a>00015 
<a name="l00016"></a>00016 <span class="preprocessor">#include &lt;list&gt;</span>
<a name="l00017"></a>00017 <span class="preprocessor">#include &lt;iostream&gt;</span>
<a name="l00018"></a>00018 
<a name="l00019"></a>00019 __GTL_BEGIN_NAMESPACE
<a name="l00020"></a>00020     
<a name="l00028"></a><a class="code" href="a00024.html">00028</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00024.html" title="PQ-Trees.">pq_tree</a> 
<a name="l00029"></a>00029 {
<a name="l00030"></a>00030 <span class="keyword">public</span>:
<a name="l00034"></a>00034     <span class="keyword">typedef</span> <a class="code" href="a00027.html" title="List which can be reversed in .">symlist&lt;pq_node*&gt;</a> <a class="code" href="a00027.html">sons_list</a>;
<a name="l00035"></a>00035 
<a name="l00039"></a>00039     <span class="keyword">typedef</span> <a class="code" href="a00027.html" title="List which can be reversed in .">symlist&lt;pq_node*&gt;::iterator</a> sons_iterator;
<a name="l00040"></a>00040 
<a name="l00044"></a><a class="code" href="a00024.html#fea06921780eb07ddb36294b109964d0">00044</a>     <a class="code" href="a00024.html" title="PQ-Trees.">pq_tree</a>() : root(0), pert_root(0), pseudo(0), fail(0)
<a name="l00045"></a>00045     {
<a name="l00046"></a>00046     }
<a name="l00047"></a>00047     
<a name="l00056"></a>00056     <a class="code" href="a00024.html" title="PQ-Trees.">pq_tree</a>(<span class="keywordtype">int</span> <span class="keywordtype">id</span>, <a class="code" href="a00020.html" title="A node in a graph.">node</a> n, <span class="keyword">const</span> list&lt;pq_leaf*&gt;&amp; le);
<a name="l00057"></a>00057 
<a name="l00061"></a>00061     ~<a class="code" href="a00024.html" title="PQ-Trees.">pq_tree</a>();
<a name="l00062"></a>00062 
<a name="l00079"></a>00079     <span class="keywordtype">bool</span> reduce(list&lt;pq_leaf*&gt;&amp; leaves);
<a name="l00080"></a>00080 
<a name="l00099"></a>00099     <span class="keywordtype">void</span> replace_pert(<span class="keywordtype">int</span> <span class="keywordtype">id</span>,
<a name="l00100"></a>00100                       <a class="code" href="a00020.html" title="A node in a graph.">node</a> n,
<a name="l00101"></a>00101                       <span class="keyword">const</span> list&lt;pq_leaf*&gt;&amp; le,
<a name="l00102"></a>00102                       <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>* em = 0,
<a name="l00103"></a>00103                       list&lt;direction_indicator&gt;* dirs = 0);
<a name="l00104"></a>00104     
<a name="l00118"></a>00118     <span class="keywordtype">void</span> get_frontier (<a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em, list&lt;direction_indicator&gt;&amp; dirs);
<a name="l00119"></a>00119 
<a name="l00124"></a>00124     <span class="keywordtype">void</span> reset ();
<a name="l00125"></a>00125 
<a name="l00132"></a><a class="code" href="a00024.html#d5788903c1411626e69e49aaa1b6541b">00132</a>     pq_node* get_fail()
<a name="l00133"></a>00133     {
<a name="l00134"></a>00134         <span class="keywordflow">return</span> fail;
<a name="l00135"></a>00135     }
<a name="l00136"></a>00136 
<a name="l00144"></a><a class="code" href="a00024.html#b320f9d84cba3198a95cc5f33fde0813">00144</a>     <span class="keywordtype">bool</span> is_fail_root()
<a name="l00145"></a>00145     {
<a name="l00146"></a>00146         <span class="keywordflow">return</span> failed_at_root;
<a name="l00147"></a>00147     }
<a name="l00148"></a>00148 
<a name="l00158"></a>00158     sons_iterator remove_dir_ind(q_node* q_fail, sons_iterator s_it);
<a name="l00159"></a>00159 
<a name="l00168"></a>00168     <span class="keywordtype">bool</span> integrity_check () <span class="keyword">const</span>;
<a name="l00169"></a>00169 
<a name="l00170"></a>00170 <span class="comment">//    p_node* insert_P (pq_node*, sons_list&amp;);</span>
<a name="l00171"></a>00171 
<a name="l00172"></a>00172 <span class="comment">//    q_node* insert_Q (pq_node*, sons_list&amp;);</span>
<a name="l00173"></a>00173 
<a name="l00174"></a>00174 <span class="comment">//    pq_leaf* insert_leaf (pq_node*);</span>
<a name="l00175"></a>00175 
<a name="l00176"></a>00176 <span class="comment">//    void insert (pq_node*, pq_node*);</span>
<a name="l00177"></a>00177 <span class="keyword">private</span>:
<a name="l00190"></a>00190     <span class="keywordtype">bool</span> bubble_up (list&lt;pq_leaf*&gt;&amp; leaves);
<a name="l00191"></a>00191     
<a name="l00202"></a>00202     <span class="keywordtype">void</span> <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a>(pq_node* p,
<a name="l00203"></a>00203              <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em,
<a name="l00204"></a>00204              list&lt;direction_indicator&gt;&amp; dirs);
<a name="l00205"></a>00205 
<a name="l00217"></a>00217     pq_node* leads_to_blocked(pq_node* le);
<a name="l00218"></a>00218 
<a name="l00219"></a>00219     
<a name="l00232"></a>00232     <span class="keywordtype">bool</span> leads_to(pq_node* le, pq_node* other);
<a name="l00233"></a>00233 
<a name="l00234"></a>00234 
<a name="l00246"></a>00246     pq_node* where_bubble_up_failed(list&lt;pq_leaf*&gt;&amp; leaves); 
<a name="l00247"></a>00247 
<a name="l00248"></a>00248 
<a name="l00257"></a>00257     pq_node* blocked_in_subtree(pq_node* n);
<a name="l00258"></a>00258 
<a name="l00259"></a>00259 
<a name="l00260"></a>00260     <span class="comment">//</span>
<a name="l00261"></a>00261     <span class="comment">// Template Matchings</span>
<a name="l00262"></a>00262     <span class="comment">//</span>
<a name="l00263"></a>00263 
<a name="l00264"></a>00264     <span class="comment">//---------------------------------------------------------- P-Templates</span>
<a name="l00265"></a>00265     
<a name="l00270"></a>00270     <span class="keywordtype">bool</span> P1 (p_node* x, <span class="keywordtype">bool</span>);
<a name="l00271"></a>00271 
<a name="l00276"></a>00276     <span class="keywordtype">bool</span> P2 (p_node* x);
<a name="l00277"></a>00277 
<a name="l00282"></a>00282     <span class="keywordtype">bool</span> P3 (p_node* x);
<a name="l00283"></a>00283 
<a name="l00288"></a>00288     <span class="keywordtype">bool</span> P4 (p_node* x);
<a name="l00289"></a>00289 
<a name="l00294"></a>00294     <span class="keywordtype">bool</span> P5 (p_node* x);
<a name="l00295"></a>00295 
<a name="l00300"></a>00300     <span class="keywordtype">bool</span> P6 (p_node* x);
<a name="l00301"></a>00301 
<a name="l00302"></a>00302     <span class="comment">//---------------------------------------------------------- Q-Templates</span>
<a name="l00303"></a>00303     
<a name="l00308"></a>00308     <span class="keywordtype">bool</span> Q1 (q_node* x, <span class="keywordtype">bool</span>);
<a name="l00309"></a>00309 
<a name="l00314"></a>00314     <span class="keywordtype">bool</span> Q2 (q_node* x, <span class="keywordtype">bool</span>);
<a name="l00315"></a>00315 
<a name="l00320"></a>00320     <span class="keywordtype">bool</span> Q3 (q_node* x);
<a name="l00321"></a>00321 
<a name="l00322"></a>00322 
<a name="l00323"></a>00323     <span class="comment">//</span>
<a name="l00324"></a>00324     <span class="comment">// Data</span>
<a name="l00325"></a>00325     <span class="comment">//</span>
<a name="l00326"></a>00326 
<a name="l00331"></a>00331     list&lt;pq_node*&gt; clear_me;
<a name="l00332"></a>00332 
<a name="l00337"></a>00337     pq_node* root;
<a name="l00338"></a>00338 
<a name="l00343"></a>00343     pq_node* pert_root;
<a name="l00344"></a>00344 
<a name="l00353"></a>00353     q_node* pseudo;
<a name="l00354"></a>00354 
<a name="l00359"></a>00359     pq_node* fail;
<a name="l00360"></a>00360 
<a name="l00365"></a>00365     <span class="keywordtype">bool</span> failed_at_root;
<a name="l00366"></a>00366 
<a name="l00372"></a>00372     <span class="keywordtype">int</span> pert_leaves_count;
<a name="l00373"></a>00373 
<a name="l00374"></a>00374     <span class="comment">//</span>
<a name="l00375"></a>00375     <span class="comment">// Friends</span>
<a name="l00376"></a>00376     <span class="comment">//</span>
<a name="l00377"></a>00377 
<a name="l00382"></a>00382     GTL_EXTERN <span class="keyword">friend</span> ostream&amp; operator&lt;&lt; (ostream&amp;, <span class="keyword">const</span> <a class="code" href="a00024.html" title="PQ-Trees.">pq_tree</a>&amp;);
<a name="l00383"></a>00383 };
<a name="l00384"></a>00384 
<a name="l00385"></a>00385 __GTL_END_NAMESPACE
<a name="l00386"></a>00386 
<a name="l00387"></a>00387 <span class="preprocessor">#endif</span>
<a name="l00388"></a>00388 <span class="preprocessor"></span>
<a name="l00389"></a>00389 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00390"></a>00390 <span class="comment">//   end of file</span>
<a name="l00391"></a>00391 <span class="comment">//--------------------------------------------------------------------------</span>
</pre></div>    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>
